import random
import copy
from LinkListCircle import *

c_ij = [
    [0,5,21,13,6,15,12,20],
    [5,0,16,18,7,12,19,17],
    [21,16,0,33,16,7,17,11],
    [13,18,33,0,17,26,16,29],
    [6,7,16,17,0,9,12,14],
    [15,12,7,26,9,0,10,5],
    [18,19,17,16,12,10,0,13],
    [20,17,11,29,14,5,13,0]
]
N = len(c_ij)
inf = 100000

def get_p_neibor(p,node,c_ij):
    neighbor = []
    for i in range(N):
        if len(neighbor) < p and i != node:
            neighbor.append(i)
        else:
            temp = i
            temp2 = temp
            for j in range(len(neighbor)):
                if c_ij[node][temp] <= c_ij[node][neighbor[j]] and temp != node:
                    temp2 = neighbor[j]
                    neighbor[j] = temp
                    temp = temp2
                else:
                    pass
    return neighbor
# print(get_p_neibor(4,4,c_ij))
def get_leng(visited,c_ij):
    leng = 0
    p = visited._head
    while p != visited._rear:
        leng += c_ij[p.elem][p.next.elem]
        p = p.next
    leng += c_ij[p.elem][p.next.elem]
    return leng
    
def GENI(visited,waiting,leng,c_ij,p):
    visited.printall
    
    def type1(k,i,j,l,route):
        route1 = copy.deepcopy(route)
        node_i,node_j,node_l = route1.is_in(i),route1.is_in(j),route1.is_in(l)
        
        stack1 = []
        p = node_i.next
        while p != node_j.next:
            stack1.append(p.elem)
            p = p.next
        
        stack2 = []
        p = node_j.next
        while p != node_l.next:
            stack2.append(p.elem)
            p = p.next
        

        route11 = LList()
        p = node_l.next
        while p != node_i.next:
            route11.append(p.elem)
            p = p.next
        
        route11.append(k)
        
        while stack1:
            route11.append(stack1.pop())
        
        while stack2:
            route11.append(stack2.pop())
        return route11,get_leng(route11,c_ij)

    def type2(k,i,j,l,m,route):
        route2 = copy.deepcopy(route)
        
        #print(k,i,j,l,m)
        node_i,node_j,node_l,node_m = route2.is_in(i),route2.is_in(j),route2.is_in(l),route2.is_in(m)

        stack1 = []
        p = node_i.next
        while p != node_m.next:
            stack1.append(p.elem)
            p = p.next
        #print(stack1)
        stack2 = []
        p = node_m.next
        while p != node_j.next:
            stack2.append(p.elem)
            p = p.next
        #print(stack2)

        route22 = LList()
        p = node_l.next
        while p != node_i.next:
            route22.append(p.elem)
            p = p.next
        route22.append(k)
        p = node_j
        while stack2:
            route22.append(stack2.pop())
        p = node_j.next
        while p != node_l.next:
            route22.append(p.elem)
            p = p.next
        while stack1:
            route22.append(stack1.pop())
        return route22,get_leng(route11,c_ij)
    
    #确定插入需要的各个点
    leng_ = leng
    visited_GENI = copy.deepcopy(visited)
    
    waiting_GENI = list(waiting)
    while waiting_GENI:
        visited_GENI.printall()
        k = random.choice(waiting_GENI)
        neighbor_k = get_p_neibor(p,k,c_ij)
        tem_leng = inf
        tem_route = copy.deepcopy(visited_GENI)
        
        #找到i和j的枚举范围
        range_i = []
        for num in neighbor_k:
            if tem_route.is_in(num):
                range_i.append(num)
        # print(range_i)
        icount = 0
        while icount <= len(range_i)-1:
            # print('icount:',icount)
            i = range_i[icount]
            
            range_j = list(range_i)
            range_j.remove(i)
            # print(range_j)
            jcount = 0
            while jcount <= len(range_j)-1 :
                j = range_j[jcount]
                
                #获取l的枚举范围
                neighbor_ii = get_p_neibor(p,visited_GENI.is_in(i).next.elem,c_ij)
                #print('neighborii',neighbor_ii)
                range_l = []
                for num in neighbor_ii:
                    if visited_GENI.is_in(num) and visited_GENI.is_between(j,i,num):
                        range_l.append(num)
                #print(i,j)
                #print('range_l:',range_l)
               # print("range_l",range_l)
                #获取m的枚举范围
                neighbor_jj = get_p_neibor(p,visited_GENI.is_in(j).next.elem,c_ij)
                range_m = []
                for num in neighbor_jj:
                    if visited_GENI.is_in(num) and visited_GENI.is_between(i,j,num):
                        range_m.append(num)
                #print("range_m",range_m)
                
                lcount = 0
                while lcount  < len(range_l):
                    l = range_l[lcount]
                    route11,leng11 = type1(k,i,j,l,visited_GENI)
                    if tem_leng >= leng11:
                        tem_route,tem_leng = route11,leng11

                    mcount = 0
                    while mcount < len(range_m):
                        m = range_m[mcount]
                        route2,leng2 = type2(k,i,j,l,m,visited_GENI)
                        if tem_leng >= leng2:
                            tem_route,tem_leng = route2,leng2
                        mcount += 1
                    lcount += 1
                jcount += 1
            icount += 1
        visited_GENI.printall
        print('waiting:',waiting_GENI)
        visited_GENI = copy.deepcopy(tem_route)
        print("leng_:",leng_)
        
        leng_ = tem_leng
        waiting_GENI.remove(k)
   
    return visited_GENI,leng_

random_visited = random.sample(range(8),3)
print(random_visited)
leng = 0
visited = LList()
waiting = list(range(8))
for i in range(3):
    visited.append(random_visited[i])
    leng += c_ij[random_visited[i]][random_visited[i-1]]
    waiting.remove(random_visited[i])

route,leng_ = GENI(visited,waiting,leng,c_ij,5)
route.printall()
print(leng_)


